import java.util.Arrays;

public class Solution {
    // 判断字符是否唯一
    public boolean isUnique(String astr) {
        int n = 0;
        for(int i = 0; i < astr.length(); i++) {
            int index = astr.charAt(i);
            if ( ((n >> index) & 1) == 0) {
                n |= (1 << index);
            } else {
                return false;
            }
        }
        return true;
    }

    // 位1的个数
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    // 比特位计数
    public int[] countBits(int n) {
        int[] count = new int[n +1];
        for(int i = 1; i <= n; i++) {
            int num = 0;
            int k = i;
            while(k > 0) {
                k &= (k - 1);
                num++;
            }
            count[i] = num;
        }
        return count;
    }

    // 汉明距离
    public int hammingDistance(int x, int y) {
        int num = x ^ y;
        int count = 0;
        while(num > 0) {
            num &= (num - 1);
            count++;
        }
        return count;
    }

    // 只出现一次的数字
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    // 两整数之和
    public int getSum(int a, int b) {
        while(b != 0) {
            int sum = a ^ b;
            int carray = (a & b) << 1;
            a = sum;
            b = carray;
        }
        return a;
    }

    // 只出现一次的数字II
    public int singleNumber2(int[] nums) {
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int count = 0;
            // 计算第 i 位
            for(int j = 0; j < nums.length; j++) {
                count += ((nums[j] >> i) & 1);
            }
            count %= 3;
            res = res | (count << i);
        }
        return res;
    }

    // 只出现一次的数字III
    public int[] singleNumber3(int[] nums) {
        int len = nums.length;
        if (len <= 2) {
            return nums;
        }
        int sum = 0; // 两数异或的结果
        for(int i = 0; i < len; i++) {
            sum ^= nums[i];
        }
        int ret1 = sum & ( -sum); // 两数不同的最低位
        int ret2 = 0;
        for(int i = 0; i < len; i++) {
            if ((nums[i] & ret1) == 0) {
                ret2 ^= nums[i];
            }
        }
        ret1 = ret2 ^ sum;
        return new int[] {ret1, ret2};
    }

    // 消失的两个数字
    public int[] missingTwo(int[] nums) {
        int sum = 0;
        int len = nums.length;
        // 求两数异或的值
        for(int i = 1; i <= len + 2; i++) {
            sum ^= i;
        }
        for(int i = 0; i < len; i++) {
            sum ^= nums[i];
        }
        int ret1 = sum & (-sum);
        int ret2 = 0;
        for(int i = 1; i <= len + 2; i++) {
            if ((i & ret1) == 0) {
                ret2 ^= i;
            }
        }
        for(int i = 0; i < len; i++) {
            if ((nums[i] & ret1) == 0) {
                ret2 ^= nums[i];
            }
        }
        ret1 = sum ^ ret2;
        return new int[] {ret1, ret2};
    }

    // 快排
    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = findPivot(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    private int findPivot(int[] nums, int start, int end) {
        int pivot = nums[start];
        int left = start;
        int right = end;
        while (left < right) {
            while (right > 0 && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    // 二分查找
    public int getPos(int[] A, int n, int val) {
        // write code here
        int left = 0;
        int right = n - 1;
        int mid = (left + right) / 2;
        while(left < right) {
            if (A[mid] < val) {
                left = mid + 1;
            } else {
                right = mid;
            }
            mid = (left + right) / 2;
        }
        return A[left] == val ? left: -1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {11, 27, 28, 33};
        solution.getPos(nums, 4, 28);
        solution.quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
